/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-integers-map-reduce
   @Language: C++
   @Datetime: 20-01-14 19:59
   */

/**
 * Definition of Input:
 * template<class T>
 * class Input {
 * public:
 *     bool done(); 
 *         // Returns true if the iteration has elements or false.
 *     void next();
 *         // Move to the next element in the iteration
 *         // Runtime error if the iteration has no more elements
 *     T value();
 *        // Get the current element, Runtime error if
 *        // the iteration has no more elements
 * }
 */
class SortIntegersMapper: public Mapper {
public:
	void Map(int _, Input<vector<int>>* input) {
		// Write your code here
		// Please directly use func 'output' to output 
		// the results into output buffer.
		// void output(string &key, vector<int>& value);
		for(; !input->done(); input->next()){
			vector<int> v=input->value();
			sort(v.begin(), v.end());
			string key = "key";
			output(key, v);
		}
	}
};


class SortIntegersReducer: public Reducer {
public:
	void Reduce(string &key, vector<vector<int>>& input) {
		// Write your code here
		// Please directly use func 'output' to output 
		// the results into output buffer.
		// void output(string &key, vector<int>& value);
		vector<int> res;
		for(const auto &v:input){
			int mid = res.size();
			res.insert(res.end(),v.begin(),v.end());
			inplace_merge(res.begin(), res.begin()+mid, res.end());
		}
		output(key, res);
	}
};
